package com.captain.lc.动态规划;

/**
 * des:
 * <p>
 * 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
 * <p>
 * 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
 * <p>
 * 示例：
 * <p>
 * 输入：nums: [1, 1, 1, 1, 1], S: 3
 * 输出：5
 *
 * @author captain
 * @date 2021/11/1 0:00
 */
public class FindTargetSumWays494 {

    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int t = sum - target;
        if (t < 0 || t % 2 != 0) {
            return 0;
        }
        int m = t / 2;
        int[] dp = new int[m + 1];
        //初始化
        dp[0] = 1;
        //滚动数组
        for (int num : nums) {
            for (int j = m; j >= num; j--) {
                dp[j] = dp[j] + dp[j - num];
            }
        }
        return dp[m];
    }

    public static void main(String[] args) {
        System.out.println(new FindTargetSumWays494().findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
    }
}
